package com.xiyou.week06.greedy;

import java.util.HashMap;

/**
 * 860. 柠檬水找零
 *
 * @ClassName：LemonadeChange
 * @Author：西柚
 * @Date：2022/2/24 11:47 上午
 * @Versiion：1.0
 */
public class LemonadeChange {
    HashMap<Integer, Integer> coins = new HashMap<Integer, Integer>();

    /**
     * 输入：bills = [5,5,5,10,20]
     * 输出：true
     * 解释：
     * 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
     * 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
     * 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
     * 由于所有客户都得到了正确的找零，所以我们输出 true。
     *
     * @param bills
     * @return
     */
    public boolean lemonadeChange(int[] bills) {
        coins.put(5, 0);
        coins.put(10, 0);
        coins.put(20, 0);

        for (int bill : bills) {
            coins.put(bill, coins.get(bill) + 1);
            if (!exchange(bill - 5)) {
                return false;
            }
        }
        return true;
    }

    private boolean exchange(int amount) {
        for (int x : new int[]{20, 10, 5}) {
            while (amount >= x && coins.get(x) > 0) {
                amount -= x;
                coins.put(x, coins.get(x) - 1);
            }
        }
        return amount == 0;
    }

    public static void main(String[] args) {
        int[] bills = new int[]{5, 5, 5, 10, 20};

        LemonadeChange lemonadeChange = new LemonadeChange();
        System.out.println(lemonadeChange.lemonadeChange(bills));
    }
}
